package a06_栈与队列;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <p>
 * a06_滑动窗口最大值
 * </p>
 *
 * @author flyduck
 * @since 2024-08-14
 */
public class a07_滑动窗口最大值复习1 {

    public static void main(String[] args) {
//        Deque<Integer> deque = new LinkedList<>();
//        deque.push(1);
//        deque.push(2);
//        deque.push(3);
//        System.out.println("deque.peekFirst() = " + deque.peekFirst());//3
//        System.out.println("deque.peekLast() = " + deque.peekLast());//1


//        int[] ints = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        int[] ints = maxSlidingWindow(new int[]{1}, 1);
        System.out.println(ints);
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        MyDeque2 myDeque2 = new MyDeque2();
        //先让k-1个元素放入
        for (int i = 0; i < k - 1; i++) {
            myDeque2.push(nums[i]);
        }
        int[] maxArray = new int[nums.length - (k - 1)];
        for (int i = k - 1; i < nums.length; i++) {
            if(i > (k - 1)){//需要pop
                myDeque2.pop(nums[i - k]);
            }
            myDeque2.push(nums[i]);
            maxArray[i - (k - 1)] = myDeque2.getMax();
        }
        return maxArray;

    }
}

class MyDeque2{

    private Deque<Integer> deque;

    public MyDeque2() {
        this.deque = new LinkedList<>();
    }

    public void push(int val){
        while (!deque.isEmpty() && deque.peekFirst() < val) {
            deque.pollFirst();
        }
        deque.push(val);
    }

    public void pop(int val){
        if(deque.peekLast().equals(val)){
            deque.pollLast();
        }
    }

    public int getMax(){
        return deque.peekLast();
    }
}

